package com.itzmn.newcode.offer;

import java.util.ArrayList;
import java.util.LinkedList;

/**
 * @Author: 张梦楠
 * @Date: 2018/11/13 16:35
 * 简书：https://www.jianshu.com/u/d611be10d1a6
 * 码云：https://gitee.com/zhangqiye
 * @Description:  剑指Offer将数变成镜像树
 *
 *  思路：
 *   判断该节点是否有左右子树，有一个就交换，同时没有就不换
 *
 */
public class MirrorBinTree {


    public static void main(String[] args) {


        new MirrorBinTree().init();
    }

    public void init(){
        int[] ints = {7,5,8,3,6,9,2};
        TreeNode binSearchTree = createBinSearchTree(ints);

        ArrayList<Integer> cengxubianli = cengxubianli(binSearchTree);
        int[] ints1 = new int[cengxubianli.size()];
        for (int i=0;i<cengxubianli.size();i++){

            ints1[i]=cengxubianli.get(i);
        }
        System.out.println(ints1);

        MirroTree(binSearchTree);
        ArrayList<Integer> cengxubianli1 = cengxubianli(binSearchTree);
        System.out.println(cengxubianli1);

    }

    public void MirroTree(TreeNode root){

        if (root == null){
            return;
        }
        if (root.left == null && root.right == null){
            return;
        }

        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;

        if (root.left != null){
            MirroTree(root.left);
        }
        if (root.right != null){
            MirroTree(root.right);
        }
    }

    public ArrayList<Integer> cengxubianli(TreeNode root){

        ArrayList<Integer> integers = new ArrayList<>();


        LinkedList<TreeNode> integers1 = new LinkedList<>();

        integers1.add(root);

        while (!integers1.isEmpty()){

            TreeNode poll = integers1.poll();

            System.out.print(poll.val+" ");
            integers.add(poll.val);
            if (poll.left!=null){
                integers1.add(poll.left);
            }
            if (poll.right!=null){
                integers1.add(poll.right);
            }

        }

        System.out.println();
        return integers;

    }


    /**
     *  根据数组创建二叉搜索树
     * @param arrs
     * @return
     */
    public TreeNode createBinSearchTree(int[] arrs){

        if (arrs.length==0){
            return null;
        }
        TreeNode root = new TreeNode(arrs[0]);

        TreeNode temproot = root;

        for (int i=1;i<arrs.length;i++){

            while (temproot != null){
                //如果传入的值比根节点大
                if (arrs[i]>=temproot.val){

                    //如果该节点存在右子节点，转换根节点
                    if (temproot.right!=null){
                        temproot = temproot.right;
                    }
                    //如果不存在右子节点，直接将数据插入右子节点
                    else {
                        TreeNode treeNode = new TreeNode(arrs[i]);
                        temproot.right =treeNode;
                        temproot = root;
                        break;
                    }
                }
                //如果传入的值比根节点小
                else {

                    if (temproot.left!=null){
                        temproot = temproot.left;
                    }else {
                        TreeNode treeNode = new TreeNode(arrs[i]);
                        temproot.left=treeNode;
                        temproot = root;
                        break;
                    }

                }
            }

        }
        return root;
    }

    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;

        }

    }



}
